package com.zh.note.huawei.onehundred.阿里巴巴找黄金宝箱4;

import java.util.*;
import java.util.ArrayDeque;
import java.util.Deque;

/**
 * https://dream.blog.csdn.net/article/details/130962549
 */
class Main {
    public static int[] solveMethod(int[] nums) {
        Deque<Integer> stack = new ArrayDeque<>();
        int[] res = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.peekFirst()] < nums[i]) {
                int index = stack.pop();//移除头
                res[index] = nums[i];
            }
            stack.push(i);//添加到头
        }

        while (!stack.isEmpty()) {
            boolean flag = false;// 没找到，自己本身就是最大的
            int index = stack.pop();
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] > nums[index]) {
                    flag = true;
                    res[index] = nums[i];
                    break;
                }
            }
            if (!flag) {
                res[index] = -1;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        // Scanner in = new Scanner(System.in);
        //
        // String inputStr = in.nextLine();
        String inputStr = "3,4,5,6,3";
        int[] nums = Arrays.stream(inputStr.split(",")).mapToInt(
                Integer::parseInt).toArray();
        int[] result = solveMethod(nums);
        String ret = "";

        for (int num : result) {
            ret += num + ",";
        }

        System.out.println(ret.substring(0, ret.length() - 1));

    }
}

